There are many distribution or transportation situations in which a network of defined delivery paths are used to transport a commodity or product between a plurality of sources of the product to a plurality of end users or loads. For example, a ship has a network of pipes to transport water from one or more pumps to a plurality of end user loads throughout the ship. Natural gas originating at a plurality of gas wells is transported across the country to a plurality of end users, using a network of gas lines. Ground transportation of products from warehouses to stores is made possible by either a network of roads and/or rail lines. In each situation, every segment of the network of defined delivery paths can be assigned a weight value indicative of the cost associated with using the segment. The weight value might be the distance of the segment, a maximum travel speed along the segment, etc., or be representative of some combination of physical attributes. In each case, the weight values are used to devise an optimal distribution solution using the network of defined delivery paths. Further, the optimal distribution solution is often dynamic as changes in the network (e.g., a broken pipe, a road or rail line out of service, etc.) necessitate a re-calculation of the distribution solution.
Existing methods of devising a solution for such complex distribution problems include those based on sets of linear equations which have to be minimized and solved simultaneously. The number of equations required is determined from the number N of points or nodes interconnecting the segments of the defined delivery paths. To analyze each combination, 2.sup.N equations must be solved simultaneously. Accordingly, this method becomes inefficient as the computational complexity increases with the number of interconnecting nodes.
Two other optimization approaches have been developed to solve some distribution situations. One approach is known in the art as the Minimum Spanning Tree (MST) algorithm and the other is known in the art as the Shortest-Path Tree (SPT) algorithm. A detail description of the MST and SPT algorithms can be found in Chapter 9 of "Introductory Management Science, Second Edition", G. D. Eppen et al., Prentice Hall Inc., 1987. Briefly, the MST is an optimization routine that generates a minimum total path for connecting all nodes in a network of defined delivery paths. The SPT finds the minimum paths linking a source of product to all nodes in the network. However, neither the MST or SPT approaches can be used to solve the afore-described multiple source to multiple load distribution problem.